package 回溯;
import java.util.List;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
public class leetcode93复制ip地址 {
	// 失败版本   这个题 说实话  与那个 左程云  面试 facebook 原题 这两个题 是有点类似的 结合那个题 做总结  
	
	
//	StringBuilder path= new StringBuilder(20);
	public static void main(String []args) {
		List<String> ans =new ArrayList<>();
//		int res=function(6);
//		System.out.println(res);
//		
		String s = "101023";
		System.out.println(new leetcode93复制ip地址().solution(s));
	}
	
	public List<String> solution(String str){
		List<String> ans = new ArrayList<>();
		int len = str.length();
		if(len < 4 || len > 12)
			return ans;
	
//		StringBuilder path = new StringBuilder();
		Deque<String> path = new ArrayDeque<>();
//		process();
		dfs(0,ans,path,len,0,str);
		return ans;
	}
	/**
	 * 这个题 之前  可能有 一些误解的！
	 */
	public void dfs(int index,List<String> ans,Deque<String> path,int len,int splitCount,String str) {
		if(index == len) {
			if(splitCount == 4)
				ans.add(String.join(".", path));
			return ;	
		}
		// 剪枝 操作 ！
		if(len - index < 4 - splitCount || len - index > 3 *( 4 - splitCount))
			return ;
			
		for(int i = 0;i < 3;i++) {	
			if(index + i >= len)
				break;
			int temp = judgeValid(str,index,index + i);
			if(temp != -1) {
				// 不得不说 写的 是真好！
//				str.substring(index, index + i + 1);
				path.addLast(temp + "");
				dfs(index + i + 1,ans,path,len,splitCount + 1,str);
				path.removeLast();
			}
		}		
	}
	
	
	public int judgeValid(String str,int start,int end) {
		// 超过两位数，就不能 以  0 开头了
		int len = end - start  + 1;
		if(len > 1 && str.charAt(start) == '0')
			return -1;
		
        // 转成 int 类型  ,下面的代码 其实 写的是很妙的 ！
//        int res = 0;
//        for (int i = left; i <= right; i++) {
//            res = res * 10 + s.charAt(i) - '0';
//        }

		int ans = Integer.parseInt(str.substring(start,end + 1));
		if(ans > 255)
			return  -1;
		return ans;
		
	}
	
	
	
	
	
	// ---------------------------------------------------------------------
	
	//  失败 版本！
	public void process(int index,List<String> ans,StringBuilder path,String str,int len) {
		if(checkPoint(path) == 3) {
			ans.add(path.toString());
			return ;
		}
		if(index >= len)
			return ;
		int flag = judge(str.charAt(index),str,index);
			path.append(str.charAt(index));
			if(checkPoint(path) < 3)
			path.append('.');
			process(index + 1,ans,path,str,len);
			// 回溯
			path.delete(path.length() -1, path.length());
			
		 if(flag == 2) {
			if(checkPoint(path) != 0)
				path.append('.');
			int length = path.length();
			// 单独一个数字开头
			path.append(str.charAt(index));
			process(index + 1,ans,path,str,len);
			// 回溯！
			path.delete(length - 1, length);
			
			// 两个数字开头
			path.append(str.charAt(index));
			path.append(str.charAt(index + 1));
			process(index + 2,ans,path,str,len);
			// 回溯操作！
			path.delete(length - 2,length);
		}
		// flag == 3 ,这样的话可以有三种操作
		else {
			
		}
		
		
	}

	
	// 0 ~ 255 这个范围内，才是满足的 ip 字段范围
	public int judge(char ch,String str,int index){
		int len = str.length();
		// 0 开头的 话，只能单个 0 
		if(ch == '0')
			return 1;
		else if(ch == '1')
			return 3;
		
		else if(ch == 2) {
			if(index + 2 < len && Integer.parseInt(str.substring(index, index + 3)) <= 255)
				return 3;
			return 2;
		}
		else
			return 2;
		
	}
	
	
	
	// 判断 当前 构造成的字符串的  点的 个数！
	public int checkPoint(StringBuilder sb) {
		String s = sb.toString();
		int count = 0;
		for(char c : s.toCharArray()) {
			if(c == '.')
				count++;
		}
		return count;	
	}
}
